CS154 PROBLEM SET 2, SOLUTIONS


2.3 (a) The states of my automaton are 4-tuples, where the first three
components indicate the positions of the three levers (L will stand for
left, R for right), and the last component indicates where the last marble
fell out (C or D).  Call the start state Q.  The accepting states are
those for which the last component is D.  Here is the transition function:

states     new state on input
	      0         1
Q	  [R,L,L,C] [R,R,R,C]
*[L,L,R,C] [R,L,R,C] [L,L,L,D]
[L,R,L,C] [R,R,L,C] [R,L,R,D]
[L,R,R,C] [R,R,R,C] [L,R,L,D]
[R,L,L,C] [L,R,L,C] [L,L,R,D]
[R,L,R,C] [L,R,R,C] [R,L,L,D]
[R,R,L,C] [L,L,L,D] [L,R,R,C]
[R,R,R,C] [L,L,R,D] [R,R,L,D]
[L,L,L,D] [R,L,L,C] [R,R,R,C]
[L,L,R,D] [R,L,R,C] [L,L,L,D]
[L,R,L,D] [R,R,L,C] [R,L,R,D]
*[L,R,R,D] [R,R,R,C] [L,R,L,D]
[R,L,L,D] [L,R,L,C] [L,L,R,D]
[R,L,R,D] [L,R,R,C] [R,L,L,D]
[R,R,L,D] [L,L,L,D] [L,R,R,C]
*[R,R,R,D] [L,L,R,D] [R,R,L,D]

The starred states can never be reached, so they need not be included in
the automaton.

(b) My apologies.  I couldn't find a nice solution to this one.

(c) Here is the Mealy machine:

state    new state/output
	    on input
	    0         1
[L,L,L] [R,L,L]/C [R,R,R]/C
[L,L,R] [R,L,R]/C [L,L,L]/D
[L,R,L] [R,R,L]/C [R,L,R]/D
[L,R,R] [R,R,R]/C [L,R,L]/D
[R,L,L] [L,R,L]/C [L,L,R]/D
[R,L,R] [L,R,R]/C [R,L,L]/D
[R,R,L] [L,L,L]/D [L,R,R]/C
[R,R,R] [L,L,R]/D [R,R,L]/D

The Moore machine is the same as the DFA with the addition that accepting
states output D and rejecting states other than Q output C.  There is no
right answer for what the start state outputs, since if it outputs
anything then the output string will be one too long.

2.5

(a) attached (b) attached

(c) This can be done with 58 states.  Of these states, 31 represent all
strings whose length is less than 5.  Twenty-six of the states represent
all strings of length five with at least two 0's.  The one remaining state
is a dead state, which indicates that the string is not accepted; all
other states are accepting states.

The start state is the empty string.

The transition function merely makes sure that the state is the last five
(or fewer, when we are reading the beginning of the string) characters of
the string, except when we encounter a string without two 0's.  In this
case we go to the dead state.  Once in the dead state, all transitions
lead back to the dead state.

(d) The states are just the numbers 0 through 4, a start state called S,
and a dead state called D.  0 is the only accepting state.  The transition
function is ∂(i,a) = 2i+a mod 5, for i = 0,1,2,3,4 and a = 0,1; ∂(S,1) =
1; ∂(S,0) = D; and ∂(D,a) = D, for a = 0,1.

(e) The states are the numbers 0 through 1023.  0 is the start state.  The
accepting states are 512 through 1023.  The transition function is ∂(i,a)
= 2i+a mod 1024.

2.8

(a) attached

(b) The automaton will work as follows.  Before doing anything else, it
guesses what the string will multiply out to, right-to-left, and stores
this information in its state.  Then it reads the first character, and
initializes the running value of the left-to-right product to be this
character.  At this time the automaton may calculate what the remainder of
the string would have to multiply out to right-to-left in order for the
initial guess to be correct (there will be 0, 1, or 2 possibilities),
whence some additional non-determinis.  It stores these two pieces of
information in its state.

From here on, each time a character is read, the automaton updates the
left-to-right product by just multiplying, it doesn't change the value of
its initial guess, and it updates the value of what the rest of the string
must multiply out to based on the old value of what the rest of the string
was supposed to multiply out to.  If it turns out that one consistent
possibilities for the remainder of the string is ε and if the left-to-right
product so far is equal to the stored value of the initial guess, then the
NFA may branch into an accepting state, with no paths back out.

Now we are ready to specify more concretely the NFA.  Its states will
be q,A,B,C,F, and all three-tuples over {a,b,c}.  The initial state is
q, the accepting states are A, B, C, and F.  The transition function is
as follows:

		∂(q,ε) = {A,B,C}

		∂(A,x) = { [x,y,a] | xy = a }
		∂(B,x) = { [x,y,b] | xy = b }
		∂(C,x) = { [x,y,c] | xy = c }

		∂([u,v,w],x) = { [ux,y,w] | xy = v } ∪ { F | x = v }

		∂(F,x) = {}

for all u,v,w,x ε {a,b,c}.

(c) attached

2.9 attached

2.10 (b)

This problem can be solved by first determining a DFA that accepts all
such strings.  Then use the method described in class to convert from a
DFA to a regular expression.  The regular expression can be written in
many different ways.  One of them is

0*+ 0*1(00*1)*0*+ 0*1(00*1)*1(1+01)*(0+ε)

2.12ab attached

2.13a My apologies again.  The method that Professor Floyd showed in class
is much easier to use than the method in the book.  One regular expression
for the accepted strings is (1(1+01)*00 + 0)*

2.14

(a) Proceed as in theorem 2.4 but define
 k
R   as an odered pair consisting of the cheapest path from i to j passing through
 ij
no vertex numbered higher than k, and the cost of this path.  Make the cost
+∞ if no such path exists.  It is easy enough to see how to modifiy formulas
(2.1) on page 34 so that they recursively yield the solution.

(b) Convert to a DFA by algorithms given in class.  Proceed as above, but
define

 k
R   as an ordered n-tuple whose mth component is the number of strings of
 ij

length m from i to j not passing through any vertex numbered higher than k

2.22

Solving this formally as an equation in numbers, one gets the solution

     1               2   3
X = ---s = (1 + r + r + r + ... )s = r*s
    1-r

This is, of course, merely a formal manipulation; it proves nothing.  One
can, however, verify that this is indeed a solution to the given equation.
Then it only remains to prove that the solution is unique.

						   k
One can show by an easy induction that X contains r s for all k.  Thus,
X contains r*s.  Now we must show that X contains nothing else.  Suppose
that X does contain something else.  Let t be the shortest such string in
X that is not in r*s.  Since r does not contain ε, t is shorter than
everything in rX.  Therefore t is not in rX.  Therefore t is in s.  But
this contradicts how we chose t.  Therefore X contains nothing that is
not in r*s.  Therefore X = r*s.

Suppose now that r contains ε.  Then r*S is a solution for any set S that
contains s; this is easy to verify.  However any solution must be of this
form because one can easily show that if w is in X then r*w is also in X,
in the same way as one shows that r*s is in X.

2.24a

The states of the machine will be the numbers 0 through 7.  The transition
function is ∂(i,a) = 2i+a mod 8, for 0 ≤ i ≤ 7 and a = 1,2.  The output of
the Moore machine is A when in state 5, B when in state 6, and C
otherwise.  The output of the Mealy machine is A when entering state 5, B
when entering state 6, and C when entering any other state.